Okay.

We looked at A star search and that's something extremely, extremely simple.

It is do greedy search with an augmented function.

So g of n is actually our heuristic, instead of computing with g of n, h of n is our heuristic,

instead of that we do greedy search with g of n plus h of n where g of n is the past

cost.

An annoyance term.

Longer you virtually search the more annoyed you get.

And that's a good thing because if you're in our loop example, oops there we are, the

more time you spend going around this loop the more annoyed you get and the more attractive

this step looks.

But eventually you get so annoyed that you actually go to oradia.

So that's the idea.

And the interesting thing is that this very simple idea is enough to give us optimality.

And I just see this, the headline is, should be optimality.

I can see why I was distracted.

Okay because admissibility is the condition for that, which is why we introduced it.

Okay we looked at an example and whereas we would have found Bucharest from Arad, we would

have found Bucharest from Arad in greedy search here without this annoyance term.

We'll find the optimal path which takes the slightly longer route along the other upper

path.

Let me just go back to Romania, no the lower path.

So if you look at it, this map has been carefully doctored with that there's two good ways of

going to Bucharest.

One that has one, two, three stops and the other one that has two stops.

So the three stop one is slightly shorter.

Actually gives you the optimal solution.

In greedy search you've reached Bucharest in a way too early.

You can reach it in two steps and greedy search will actually charge down the shortest, kind

of the tree level shortest path and try finding something there.

That does not always give you the optimal solution and A star search actually also explores

this one and finds the optimal solution first, which is the good property of A star search

because it tells us the first solution we find, this one, is actually the optimal one

which means that as soon as we found one solution we can stop searching.

We stop searching here.

We're never actually going to find this solution because this would be non-optimal.

That's the nice thing about A star.

Again the other example just to have something a little bit more complicated than, complex

than Romania and the intuition behind the A star search is that if we look at these

F contours, F being straight line distance in this case plus past cost, then these are

the circles, the F circles where F is constant actually look like these ovals and those ovals

we actually have to cover everything in them.

The better our F heuristic is, the skinnier these ovals actually become.

The skinnier the ovals become, the more targeted, the more focused our search is.

Of course if you have the zero heuristic, then we have uniform cost search and these

become essentially circles.

We don't want circles, we want skinny ovals or in other words good heuristics.